package structure;

import Tree.MyBinaryTree;

import java.util.*;

public class Test10{
    public static void main(String[] args) {

    }
    //leetcode 100 相同的树
    class Solution0 {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p == null && q == null){
                return true;
            }
            if(p == null || q == null || p.val != q.val){
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }
    //leetcode 222 完全二叉树的结点个数
    class Solution {
        public int size = 0;
        public int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftSize = countNodes(root.left);
            int rightSize = countNodes(root.right);
            return leftSize + rightSize + 1;
        }
    }
    //leetcode 104 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    //leetcode 768 最多能完成排序的块 Ⅱ
    public int maxChunksToSorted(int[] arr) {
        int len = arr.length;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            int tmp = arr[i];
            if (stack.isEmpty() || tmp >= stack.peek()) {
                stack.push(tmp);
            } else {
                int max = stack.pop();
                while (!stack.isEmpty() && stack.peek() > tmp) {
                    stack.pop();
                }
                stack.push(max);
            }
        }
        return stack.size();
    }
}
